public class Leetcode {
}

//leetcode:712:两个字符串的最小ASCII删除和
class Solution1 {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length() , n = s2.length();

        //创建一个dp表，表示s1的0~i区间和s2的0~j区间所以子序列里，公共子序列的ASCII值最大和
        int[][] dp = new int[m+1][n+1];

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                //如果最后一个位置不相同就，就去判断s1的0~i-1区间和s2的0~j的所有子序列里找，公共子序列的ASCII值最大和 和 s1的0~i区间和s2的0~j-1的所有子序列里找，公共子序列的ASCII值最大和 的最大值
                dp[i][j] = Math.max(dp[i-1][j] , dp[i][j-1]);
                //如果相等此时的ASCII值最大和就为s1的0~i-1区间和s2的0~j-1的所有子序列里，公共子序列的ASCII值最大和 加上 这个位置的ASCII值
                if(s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + s1.charAt(i-1);
                }
            }
        }

        //计算两个字符串总的ASCII值和
        int sum = 0;
        for(char ch : s1.toCharArray()) sum += ch;
        for(char ch : s2.toCharArray()) sum += ch;
        //此时总的和减去公共子序列的最大ASCII值和就是我们的两个字符串的最小ASCII删除和
        return sum - dp[m][n] * 2;
    }
}

//leetcode:718:最长重复子数组
class Solution2 {
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;

        //创建一个dp表，表示nums1数组中0~i位置和nums0~j位置的公共子序列的长度
        int[][] dp = new int[m+1][n+1];

        int ret = 0;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                //如果i位置的元素和j位置的元素相同，就代表他是公共子数组
                if(nums1[i-1] == nums2[j-1]){
                    //此时的长度就为nums1的i-1和nums2的j-1位置的公共子序列的长度加1
                    dp[i][j] = dp[i-1][j-1] + 1;
                    //得到所有位置公共子序列的最长长度
                    ret = Math.max(ret , dp[i][j]);
                }
            }
        }
        return ret;
    }
}